ICPC Live Archive/4807 - Cocircular Points/4807.cpp

   1 // Accepted
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 const double EPS = 1e-9;
  29 int cmp(double x, double y = 0, double tol = EPS) {
  30     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  31 }
  32
  33 struct point {
  34     double x, y;
  35     point(double x, double y) : x(x), y(y) {}
  36     point(){}
  37     bool operator < (const point &p) const {
  38         int t = cmp(this->x, p.x);
  39         if (t != 0) return t < 0;
  40         return cmp(this->y, p.y) < 0;
  41     }
  42 };
  43
  44 point center(const point &p, const point &q, const point &r) {
  45     double ax = q.x - p.x;
  46     double ay = q.y - p.y;
  47     double bx = r.x - p.x;
  48     double by = r.y - p.y;
  49     double d = ax*by - bx*ay;
  50
  51     if (cmp(d, 0) == 0) {
  52         printf("p = <%lf, %lf>, q = <%lf, %lf>, r = <%lf, %lf>\n", p.x, p.y, q.x, q.y, r.x, r.y);
  53         printf("Points are collinear!\n");
  54         assert(false);
  55     }
  56
  57     double cx = (q.x + p.x) / 2;
  58     double cy = (q.y + p.y) / 2;
  59     double dx = (r.x + p.x) / 2;
  60     double dy = (r.y + p.y) / 2;
  61
  62     double t1 = bx*dx + by*dy;
  63     double t2 = ax*cx + ay*cy;
  64
  65     double x = (by*t2 - ay*t1) / d;
  66     double y = (ax*t1 - bx*t2) / d;
  67
  68     return point(x, y);
  69 }
  70
  71 point points[105];
  72
  73 int main(){
  74     int n;
  75     while (scanf("%d", &n) == 1) {
  76         if (n == 0) break;
  77
  78         for (int i = 0; i < n; ++i) {
  79             scanf("%lf %lf", &points[i].x, &points[i].y);
  80         }
  81
  82         if (n <= 2) {
  83             printf("%d\n", n);
  84             continue;
  85         }
  86
  87         int ans = 2;
  88         for (int i = 0; i < n; ++i) {
  89             for (int j = i + 1; j < n; ++j) {
  90                 map<point, int> times;
  91                 for (int k = 0; k < n; ++k) {
  92                     if (k == i or k == j) continue;
  93                     double x0 = points[i].x - points[k].x;
  94                     double y0 = points[i].y - points[k].y;
  95                     double x1 = points[j].x - points[k].x;
  96                     double y1 = points[j].y - points[k].y;
  97                     if ( cmp(x0*y1 - y0*x1, 0) == 0 ) continue; // collinear
  98                     point c = center(points[i], points[j], points[k]);
  99                     times[c]++;
 100                     ans = max(ans, times[c] + 2);
 101                 }
 102             }
 103         }
 104         printf("%d\n", ans);
 105     }
 106     return 0;
 107 }